package codingPractice.huawei;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Test2 {
    public static int N, K;
    public static int[][] maze;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()) {
            N = sc.nextInt();
            K = sc.nextInt();
            maze = new int[N][N];

            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    maze[i][j] = sc.nextInt();
                }
            }

            int left = 0;
            int right = Integer.MIN_VALUE;
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    right = Math.max(right, maze[i][j]);
                }
            }

            int result = right;
            while(left <= right) {
                int mid = (left + right) / 2;
                if (canReachDestination(mid)) {
                    result = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            System.out.println(result);
        }

    }

    private static boolean canReachDestination(int limit) {
        boolean[][] visited = new boolean[N][N];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0,0});
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int steps = current[2];

            if (x == N-1 && y == N-1) {
                return steps <= K;
            }

            for(int i=0;i<4;i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                    if ((nx == 0 && ny == 0) || (nx == N-1 && ny == N-1) || maze[nx][ny] <= limit) {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny, steps + 1});
                    }

                }
            }
        }
        return false;
    }
}
